package com.caoyanan.algorithm.question.zuoTraining.training003.class07;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.Arrays;

/**
 * 给定一个正数数组 arr，其中所有的值都为整数，以下是最小不可组成和的概念:
 * 把 arr 每个子集内的所有元素加起来会出现很多值，其中最小的记为 min，最大的记为max
 * 在区间[min,max]上,如果有数不可以被arr某一个子集相加得到，那么其中最小的那个数是arr 的最小不可组成和
 * 在区间[min,max]上，如果所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最 小不可组成和
 * 请写函数返回正数数组 arr 的最小不可组成和。
 * 【举例】
 * arr=[3,2,5]。子集{2}相加产生 2 为 min，子集{3,2,5}相加产生 10 为 max。
 * 在区间[2,10] 上，4、 6 和 9 不能被任何子集相加得到，其中 4 是 arr 的最小不可组成和。
 * arr=[1,2,4]。子集{1}相加产生 1 为 min，子集{1,2,4}相加产生 7 为 max。
 * 在区间[1,7]上， 任何 数都可以被子集相加得到，所以 8 是 arr 的最小不可组成和。
 * 【进阶】
 * 如果已知正数数组 arr 中肯定有 1 这个数，是否能更快地得到最小不可组成和?
 * @author: caoyanan
 * @time: 2021/5/19 1:44 下午
 */
public class Question02_SmallestUnFormedSum {

    public static void main(String[] args) {
        int times = 100000;
        for (int i = 0; i < times; i++) {
            int[] arr = LogarithmInputGenerator.getInstance()
                    .generateRandomArray(12, 100);
            arr[0] = 1;
            int result = dpMethod(arr);
            int result2 = sortMethod(arr);
            if (result != result2) {
                System.out.printf("数组:%s的最小不可组成和是:%s, %s\r\n", Arrays.toString(arr), result, result2);
            }
        }
        System.out.println("finish");

    }

    private static int sortMethod(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 1;
        }
        int range = 1;
        Arrays.sort(arr);
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] <= range + 1) {
                range += arr[i];
            } else {
                return range + 1;
            }
        }
        return range + 1;
    }


    /**
     * 动态规划方法，背包解法
     * 一维是集和元素个数，一维是子元素和 dp[i][j] 就表示 arr[0...i] 能不能累加出j这个值来，这就是一个背包问题
     *  首先第一列都是true，即不管取几个元素，和都可以是0.。然后第一行 dp[0][arr[0]]是true，其他都是false。
     *  然后 dp[i][j]状态转移方程，就是要不要arr[i]。如果不要， dp[i-1][j]是true就可以，
     *      如果要，那么需要 j > arr[i] 且 dp[i-1][j-arr[i]]是true
     *      所以， dp[i][j] = dp[i-1][j] || ( j > arr[i] && dp[i-1][j-arr[i]]
     * 填完之后，从最小值min一直加到sum，看最后一行，有没有false。没有就是sum+1
     * @param arr
     * @return
     */
    private static int dpMethod(int[] arr) {

        if (arr == null || arr.length == 0) {
            return 1;
        }
        int sum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            sum += arr[i];
        }

        boolean[][] dp = new boolean[arr.length][sum+1];

        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = true;
        }
        dp[0][arr[0]] = true;

        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= sum; j++) {
                dp[i][j] = dp[i - 1][j] || (j >= arr[i] && dp[i - 1][j - arr[i]]);
            }
        }

        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        for (int i = min+1; i <= sum; i++) {
            if (!dp[arr.length - 1][i]) {
                return i;
            }
        }
        return sum + 1;

    }
}
